//给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 
//
// 你可以对一个单词进行如下三种操作： 
//
// 
// 插入一个字符 
// 删除一个字符 
// 替换一个字符 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：word1 = "horse", word2 = "ros"
//输出：3
//解释：
//horse -> rorse (将 'h' 替换为 'r')
//rorse -> rose (删除 'r')
//rose -> ros (删除 'e')
// 
//
// 示例 2： 
//
// 
//输入：word1 = "intention", word2 = "execution"
//输出：5
//解释：
//intention -> inention (删除 't')
//inention -> enention (将 'i' 替换为 'e')
//enention -> exention (将 'n' 替换为 'x')
//exention -> exection (将 'n' 替换为 'c')
//exection -> execution (插入 'u')
// 
//
// 
//
// 提示： 
//
// 
// 0 <= word1.length, word2.length <= 500 
// word1 和 word2 由小写英文字母组成 
// 
//
// Related Topics 字符串 动态规划 👍 3145 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-19 16:40:22
 * @description 72.编辑距离
 */
public class EditDistance{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new EditDistance().new Solution();
		  solution.minDistance("horse","ros");

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //自底向上
    public int minDistance(String word1, String word2) {
		int m = word1.length();
		int n = word2.length();
		//dp[i][j]表示，0~i转化成0~j需要的步数
		//对于i,j等于0时，他们的值应该为字符串的长度
		int [][] dp=new int[m+1][n+1];
		//第0列
		for (int i = 1; i <=m; i++) {
			dp[i][0]=dp[i-1][0]+1;
		}
		//第0行
		for (int i = 1; i <=n; i++) {
			dp[0][i]=dp[0][i-1]+1;
		}
		for (int i = 1; i <=m; i++) {
			char c1 = word1.charAt(i-1);
			for (int j = 1; j <=n; j++) {
				char c2 = word2.charAt(j-1);
				if(c1==c2){
					dp[i][j]=dp[i-1][j-1];
				}else {
					/*
					相等的时候dp[i][j]= dp[i - 1][j - 1]
					插入操作：dp[i][j] = dp[i][j - 1] + 1，
					表示在 word1 中插入一个字符，然后与 word2 的第 j 个字符匹配。
					删除操作：dp[i][j] = dp[i - 1][j] + 1，
					表示删除 word1 的第 i 个字符，然后与 word2 的前 j 个字符匹配。
					替换操作：dp[i][j] = dp[i - 1][j - 1] + 1，
					表示将 word1 的第 i 个字符替换为 word2 的第 j 个字符。*/
					dp[i][j]=1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
				}
			}
		}
		return dp[m][n];
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
